package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/13.
 * 下边加右边，最后一个为1
 */
public class code62 {

    public static class Solution {
        public int uniquePaths(int m, int n) {
            int dp[][] = new int[m + 1][n + 1];
            for(int i=1;i<=m;i++) {
                for(int j=1;j<=n;j++) {
                    dp[i][j]=-1;
                }
            }
            dp[m-1][n]=1;
            dp[m][n]=1;
            dp[m][n-1]=1;
            weekHelper(1, 1, m, n,dp);
            return dp[1][1];
        }

        public int weekHelper(int i,int j,int m,int n,int[][] dp) {
            if (dp[i][j]!=-1){
                return dp[i][j];
            }
            if(i==m){
                dp[i][j] = weekHelper(i, j + 1, m, n, dp);
                return dp[i][j];
            }
            if(j==n){
                dp[i][j] = weekHelper(i+1, j, m, n, dp);
                return dp[i][j];
            }
            dp[i][j] = weekHelper(i + 1, j, m, n, dp) + weekHelper(i, j + 1, m, n, dp);
            return dp[i][j];
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.uniquePaths(2,2));
    }


}


//    leetcode simple code
//    每一步从左边来或从上边来
//    Integer[][] map = new Integer[m][n];
//    for(int i = 0; i<m;i++){
//        map[i][0] = 1;
//    }
//    for(int j= 0;j<n;j++){
//        map[0][j]=1;
//    }
//    for(int i = 1;i<m;i++){
//        for(int j = 1;j<n;j++){
//            map[i][j] = map[i-1][j]+map[i][j-1];
//        }
//    }
//    return map[m-1][n-1];

//数学解法

//https://discuss.leetcode.com/topic/2734/my-ac-solution-using-formula